      1  /**

      2     This class implements a binary search tree whose

      3     nodes hold objects that implement the Comparable

      4     interface.

      5  */

      6  public class BinarySearchTree<E extends Comparable>

      7  {

      8     private Node root;

      9

     10     /**

     11        Constructs an empty tree.

     12     */

     13     public BinarySearchTree()

     14     {

     15        root = null;

     16     }

     17

     18     /**

     19        Inserts a new node into the tree.

     20        @param obj the object to insert

     21     */

     22     public void add(E obj)

     23     {

     24        Node newNode = new Node();

     25        newNode.data = obj;

     26        newNode.left = null;

     27        newNode.right = null;

     28        if (root == null) { root = newNode; }

     29        else { root.addNode(newNode); }

     30     }

     31

     32     /**

     33        Tries to find an object in the tree.

     34        @param obj the object to find

     35        @return true if the object is contained in the tree

     36     */

     37     public boolean find(E obj)

     38     {

     39        Node current = root;

     40        while (current != null)

     41        {

     42           int d = current.data.compareTo(obj);

     43           if (d == 0) { return true; }

     44           else if (d > 0) { current = current.left; }

     45           else { current = current.right; }

     46        }

     47        return false;

     48     }

     49

     50     /**

     51        Tries to remove an object from the tree. Does nothing

     52        if the object is not contained in the tree.

     53        @param obj the object to remove

     54     */

     55     public void remove(E obj)

     56     {

     57        // Find node to be removed

     58

     59        Node toBeRemoved = root;

     60        Node parent = null;

     61        boolean found = false;

     62        while (!found && toBeRemoved != null)

     63        {

     64           int d = toBeRemoved.data.compareTo(obj);

     65           if (d == 0) { found = true; }

     66           else

     67           {

     68              parent = toBeRemoved;

     69              if (d > 0) { toBeRemoved = toBeRemoved.left; }

     70              else { toBeRemoved = toBeRemoved.right; }

     71           }

     72        }

     73

     74        if (!found) { return; }

     75

     76        // toBeRemoved contains obj

     77

     78        // If one of the children is empty, use the other

     79

     80        if (toBeRemoved.left == null || toBeRemoved.right == null)

     81        {

     82           Node newChild;

     83           if (toBeRemoved.left == null)

     84           {

     85              newChild = toBeRemoved.right;

     86           }

     87           else

     88           {

     89              newChild = toBeRemoved.left;

     90           }

     91

     92           if (parent == null) // Found in root

     93           {

     94              root = newChild;

     95           }

     96           else if (parent.left == toBeRemoved)

     97           {

     98              parent.left = newChild;

     99           }

    100           else

    101           {

    102              parent.right = newChild;

    103           }

    104           return;

    105        }

    106

    107        // Neither subtree is empty

    108

    109        // Find smallest element of the right subtree

    110

    111        Node smallestParent = toBeRemoved;

    112        Node smallest = toBeRemoved.right;

    113        while (smallest.left != null)

    114        {

    115           smallestParent = smallest;

    116           smallest = smallest.left;

    117        }

    118

    119        // smallest contains smallest child in right subtree

    120

    121        // Move contents, unlink child

    122

    123        toBeRemoved.data = smallest.data;

    124        if (smallestParent == toBeRemoved)

    125        {

    126           smallestParent.right = smallest.right;

    127        }

    128        else

    129        {

    130           smallestParent.left = smallest.right;

    131        }

    132     }

    133

    134     /**

    135        Prints the contents of the tree in sorted order.

    136     */

    137     public void inorder(Visitor<E> v)

    138     {

    139        inorder(root, v);

    140     }

    141

    142     /**

    143        Prints a node and all of its descendants in sorted order.

    144        @param parent the root of the subtree to print

    145     */

    146     private void inorder(Node parent, Visitor<E> v)

    147     {

    148        if (parent == null) { return; }

    149        inorder(parent.left, v);

    150        v.visit(parent.data);

    151        inorder(parent.right, v);

    152     }

    153

    154     /**

    155        A node of a tree stores a data item and references

    156        of the child nodes to the left and to the right.

    157     */

    158     class Node

    159     {

    160        public E data;

    161        public Node left;

    162        public Node right;

    163

    164        /**

    165           Inserts a new node as a descendant of this node.

    166           @param newNode the node to insert

    167        */

    168        public void addNode(Node newNode)

    169        {

    170           int comp = newNode.data.compareTo(data);

    171           if (comp < 0)

    172           {

    173              if (left == null) { left = newNode; }

    174              else { left.addNode(newNode); }

    175           }

    176           else if (comp > 0)

    177           {

    178              if (right == null) { right = newNode; }

    179              else { right.addNode(newNode); }

    180           }

    181        }

    182     }

    183  }